//! \file examples/Arrangement_2/ex_incremental_insertion.cpp
// Using the global incremental insertion functions.

#include <CGAL/Cartesian.h>
#include <CGAL/Quotient.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_walk_along_line_point_location.h>
#include <CGAL/Arr_enums.h>

///#include "arr_rational_nt.h"
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_extended_dcel.h>
#include <CGAL/Arr_observer.h>
#include <CGAL/MP_Float.h>

#include <list>
#include <climits>
#include <fstream>
//#define PLOTTING 1

#ifdef PLOTTING
#include <plotter.h>
#endif

#define MAXORDER 12

using namespace std;
//using namespace Arrangement_2;

#ifdef PLOTTING

void draw_c_curve (Plotter& plotter, double dx, double dy, int order)
{
  if (order >= MAXORDER)
    plotter.fcontrel (dx, dy);	// continue path along (dx, dy)
  else
    {
      draw_c_curve (plotter,
                    0.5 * (dx - dy), 0.5 * (dx + dy), order + 1);
      draw_c_curve (plotter,
                    0.5 * (dx + dy), 0.5 * (dy - dx), order + 1);
    }
}
XPlotter *plotter;

void draw()
{
	  // set a Plotter parameter
	  char page[20],type[20];
	  strcpy(page,"VIEWPORTSIZE");
	  strcpy(type,"b");
      Plotter::parampl (page, type);

      plotter=new XPlotter(cin, cout, cerr); // declare Plotter
      //PSPlotter plotter(cin, cout, cerr); // declare Plotter

	  if (plotter->openpl () < 0)          // open Plotter
	    {
	      cerr << "Couldn't open Plotter\n";
	      return ;
	    }

	  plotter->fspace (-8.0, -8.0, 8.0, 8.0); // specify user coor system
	  plotter->flinewidth (0.03);       // line thickness in user coordinates
	  plotter->pencolorname ("red");    // path will be drawn in red
	  plotter->erase ();                // erase Plotter's graphics display
	  //plotter.fmove (600.0, 300.0);    // position the graphics cursor
	  //draw_c_curve (plotter, 0.0, 400.0, 0);
	  //plotter.flushpl();
/*
	  plotter->pencolorname ("blue");    // path will be drawn in red
	  plotter->line(-1,-1,2,2);
	  plotter->pencolorname ("red");    // path will be drawn in red
	  plotter->line(-1,-1,3,2);
	  plotter->pencolorname ("green");    // path will be drawn in red
	  plotter->fline(1.0,0.5,2,2);
	  //plotter.box(
	  plotter->flushpl();
	  plotter->flushpl();
	  if (plotter->closepl () < 0)      // close Plotter
	    {
	      cerr << "Couldn't close Plotter\n";
	      return ;
	    }

	    */
	  return ;
}
#endif



#include "arr_print.h"

typedef CGAL::Quotient <CGAL::MP_Float> Number_type;
typedef CGAL::Cartesian < Number_type > Kernel;
typedef CGAL::Arr_segment_traits_2 < Kernel > Traits_2;
typedef Traits_2::Point_2 Point_2;
typedef Traits_2::X_monotone_curve_2 Segment_2;

typedef CGAL::Arr_face_extended_dcel < Traits_2, int >Dcel;
typedef CGAL::Arrangement_2 < Traits_2, Dcel > Arrangement_2;

typedef CGAL::Arr_walk_along_line_point_location < Arrangement_2 > Walk_pl;

void RSMedian_of_P(Point_2 P[], int size,
		   list < Arrangement_2::Face_handle > &out);

#define SIZE 1000




int rs_med(Point_2 P[], int size,	double *md)
{

    Arrangement_2 arr;
    Walk_pl pl(arr);

    Arrangement_2::Face_iterator faceItr;
    Arrangement_2::Ccb_halfedge_const_circulator curr;

    list < Arrangement_2::Face_handle > L;
    list < Arrangement_2::Face_handle >::iterator l, it2;

    list < Arrangement_2::Face_handle > R;
    list < Arrangement_2::Face_handle > S;
    list < Segment_2 > Seg;


    int count = 0,count2 = 0;

    // Add all segments and construct the arrangement.
    for (int i = 0; i < size; i++)
    	//insert_point(arr, P[i], pl);
	    for (int j = i + 1; j < size; j++) {
	     //   insert_curve(arr, Segment_2(P[i], P[j]), pl);
	    	Seg.push_back(Segment_2(P[i], P[j]));
	    }

    insert_curves(arr,Seg.begin(),Seg.end());
    //CGAL::insert_non_intersecting_curves(arr,Seg.begin(),Seg.end());


    /* Actual stuff starts. */

    //Label faces as infty and zero for unbounded
    for (faceItr = arr.faces_begin(); faceItr != arr.faces_end(); ++faceItr) {

	    faceItr->set_data(INT_MAX);
	    if (faceItr->is_unbounded()) {
	        faceItr->set_data(0);
	        L.push_back(faceItr);
	    }

    }

    do {
	    R = S;
	    S.erase(S.begin(), S.end());
	    count++;
	    //count2 = 0;

	    for (l = L.begin(); l != L.end(); ++l) {
	        Arrangement_2::Ccb_halfedge_circulator curr;
	        Arrangement_2::Ccb_halfedge_circulator old;
	        Arrangement_2::Halfedge_handle he;

	        // Unbounded face has hole and bounded has outer_ccb
	        if ((*l)->is_unbounded()) {
		        Arrangement_2::Hole_iterator hi;
		        hi = (*l)->holes_begin();
		        curr = *hi;
		        old = curr;
	        } else {
		        curr = (*l)->outer_ccb();
		        old = curr;
	        }

	        count2 = 0;
	        do {
		        he = curr;

		        if(he->twin()->face()->data()==INT_MAX||he->twin()->face()->data()>=count-1){
		        	count2=-1;
		        }

		        if (he->twin()->face()->data() == INT_MAX) {
		            /* Set the label */
		            //count2++;
		        	he->twin()->face()->set_data(count);
		            S.push_back(he->twin()->face());

		            //////////////////////////


		            Arrangement_2::Ccb_halfedge_circulator gui;
		            double x2,y2;

		            gui = (*(he->twin()->face())).outer_ccb();

		            Arrangement_2::Ccb_halfedge_const_circulator loop = gui;

		            Arrangement_2::Halfedge_const_handle hand = loop;

		            x2=to_double( hand->target()->point().x() );
		            y2=to_double( hand->target()->point().y() );

		            md[0]=x2;
		            md[1]=y2;

		            ///////////////////////


		        }

		        ++curr;
	        } while (curr != old);


	    }
	    L = S;

    } while (!L.empty());

    return count;
}

int rs_rings(Point_2 P[], double *ringX, double *ringY,
int* ringszArr, int size,	int* ringsz, int approx)
{

	int interval;
	ringsz[0]++;
	if (approx==1)
	{
	interval= size*size/(8*ringsz[0]);
	}
	else
	{
		interval= rs_med(P,size,ringX)/(ringsz[0]);
	}
	int ringcount1 = 0, ringcount2 = 0;

	ringsz[0] = 0;



    Arrangement_2 arr;
    Walk_pl pl(arr);

    Arrangement_2::Face_iterator faceItr;
    Arrangement_2::Ccb_halfedge_const_circulator curr;

    list < Arrangement_2::Face_handle > L;
    list < Arrangement_2::Face_handle >::iterator l, it2;

    list < Arrangement_2::Face_handle > R;
    list < Arrangement_2::Face_handle > S;
    list < Segment_2 > Seg;


    int count = 0,count2 = 0;

    // Add all segments and construct the arrangement.
    for (int i = 0; i < size; i++)
    	//insert_point(arr, P[i], pl);
	    for (int j = i + 1; j < size; j++) {
	     //   insert_curve(arr, Segment_2(P[i], P[j]), pl);
	    	Seg.push_back(Segment_2(P[i], P[j]));
	    }

    insert_curves(arr,Seg.begin(),Seg.end());
    //CGAL::insert_non_intersecting_curves(arr,Seg.begin(),Seg.end());


    /* Actual stuff starts. */

    //Label faces as infty and zero for unbounded
    for (faceItr = arr.faces_begin(); faceItr != arr.faces_end(); ++faceItr) {

	    faceItr->set_data(INT_MAX);
	    if (faceItr->is_unbounded()) {
	        faceItr->set_data(0);
	        L.push_back(faceItr);
	    }

    }

    do {
	    R = S;
	    S.erase(S.begin(), S.end());
	    count++;
	    //count2 = 0;

	    for (l = L.begin(); l != L.end(); ++l) {
	        Arrangement_2::Ccb_halfedge_circulator curr;
	        Arrangement_2::Ccb_halfedge_circulator old;
	        Arrangement_2::Halfedge_handle he;

	        // Unbounded face has hole and bounded has outer_ccb
	        if ((*l)->is_unbounded()) {
		        Arrangement_2::Hole_iterator hi;
		        hi = (*l)->holes_begin();
		        curr = *hi;
		        old = curr;
	        } else {
		        curr = (*l)->outer_ccb();
		        old = curr;
	        }

	        count2 = 0;
	        do {
		        he = curr;

		         if (he->twin()->face()->data() == INT_MAX) {

		            /* Set the label */
		            //count2++;
		        	he->twin()->face()->set_data(count);
		            S.push_back(he->twin()->face());
		            //////////////////////////
		            Arrangement_2::Ccb_halfedge_circulator gui;
		            double x2,y2;

		            gui = (*(he->twin()->face())).outer_ccb();
		            Arrangement_2::Ccb_halfedge_const_circulator loop = gui;
		            Arrangement_2::Halfedge_const_handle hand = loop;
		            x2=to_double( hand->target()->point().x() );
		            y2=to_double( hand->target()->point().y() );

		            ///////Add point to current ring if it is part of any ring
		            if( (count%interval)==0 )
		            {
		            	ringX[ringcount1]=x2;
		            	ringY[ringcount1]=y2;
		            	ringcount1++;
		            	ringcount2++;
		            }
		        }

		        ++curr;
	        } while (curr != old);


	    }

	    if(ringcount2>0)
	    {
	    	ringszArr[ringsz[0]++]=ringcount2;
	    	ringcount2=0;
	    }

	    L = S;

    } while (!L.empty());

    return 1;
}



extern "C" {

void rs_rings(double* x,double* y, double* ringX,double *ringY,
		int * ringszArr, int*sz, int *ringsz, int *approx)
{
	Point_2 p[400];

		for (int i = 0; i < sz[0]; i++) {
			p[i] = Point_2(x[i], y[i]);
		}
		rs_rings(p, ringX, ringY, ringszArr, sz[0],	ringsz, approx[0]);
}

	void rs_median(double* x,double* y, double *md,int * sz)
	{

		Point_2 p[400];

		for (int i = 0; i < sz[0]; i++) {
			p[i] = Point_2(x[i], y[i]);
		}

		rs_med(p, sz[0], md);
	}

}

int main()
{
	//readloud();
	//read4();
	//read2();
	//return 0;
    // Construct the arrangement of five intersecting segments.
    Arrangement_2 arr;
    Walk_pl pl(arr);

#ifdef PLOTTING
    draw();
#endif

    int n;
    double x, y;
    ifstream in("/home/mudassir/ws/in.txt");
    in>>n;
    //std::cin >> n;

    Point_2 p[400], convp[400];

    for (int i = 0; i < n; i++) {
	in >> x >> y;
	p[i] = Point_2(x, y);

#ifdef PLOTTING
	plotter->fpoint(x,y);
#endif
    }


    list < Arrangement_2::Face_handle > output;
    list < Arrangement_2::Face_handle >::iterator itr;

    //RSMedian_of_P(p, n, output);

#ifdef PLOTTING
    plotter->closepl();
#endif

    std::cout << "\nDepth:\n"<<(*output.begin())->data()<<"in "<<output.size()<<"faces.";

    int count =0;
    for (itr = output.begin(); itr != output.end(); ++itr){
	    //print_face< Arrangement_2 >(*itr);

    	Arrangement_2::Ccb_halfedge_const_circulator circ = (*itr)->outer_ccb();
    	{
    		Arrangement_2::Ccb_halfedge_const_circulator curr = circ;
    	  convp[count++]=curr->source()->point();
    	  cout<<convp[count];
    	  // add point to output: curr->source()->point();

    	  do {
    		//assign to the circulator instead of its handle
    	    Arrangement_2::Halfedge_const_handle he = curr;
    	    // add point to output: he->target()->point() ;
    	    convp[count++] = he->target()->point() ;

    	  } while (++curr != circ);

    	}
    	//print_face();
    }


    /*
    for (itr = output.begin(); itr != output.end(); ++itr){
	    //print_face< Arrangement_2 >(*itr);
	    std::cout << "Label: " << (*itr)->data() << std::endl;
    }*/
    //now you have all the points of the thing now go and find its convex hull
    return (0);
}

